{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #心算挑战"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxmiumScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #心算挑战"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "「力扣挑战赛」心算项目的挑战比赛中，要求选手从 `N` 张卡牌中选出 `cnt` 张卡牌，若这 `cnt` 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 `cnt` 张卡牌数字总和。\n",
    "给定数组 `cards` 和 `cnt`，其中 `cards[i]` 表示第 `i` 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`cards = [1,2,8,9], cnt = 3`\n",
    ">\n",
    ">输出：`18`\n",
    ">\n",
    ">解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`cards = [3,3,1], cnt = 1`\n",
    ">\n",
    ">输出：`0`\n",
    ">\n",
    ">解释：不存在获取有效得分的卡牌方案。\n",
    "\n",
    "**提示：**\n",
    "- `1 <= cnt <= cards.length <= 10^5`\n",
    "- `1 <= cards[i] <= 1000`\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [uOAnQW](https://leetcode.cn/problems/uOAnQW/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [uOAnQW](https://leetcode.cn/problems/uOAnQW/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,8,9]\\n3', '[3,3,1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort() \n",
    "        odd_list = []\n",
    "        even_list = []\n",
    "        sum = 0\n",
    "        for i in range(cnt):\n",
    "            sum=cards[-1]+sum\n",
    "            if cards[-1]%2==0:\n",
    "                odd_list.append(cards[-1])\n",
    "            else:\n",
    "                even_list.append(cards[-1])\n",
    "            cards.pop()\n",
    "            \n",
    "        if sum%2==0:\n",
    "            return sum\n",
    "\n",
    "        odd_card = []\n",
    "        even_card = []\n",
    "        for i in cards:\n",
    "            if i%2==0:\n",
    "                odd_card.append(i)\n",
    "            else:\n",
    "                even_card.append(i)\n",
    "        \n",
    "        sum_1 = 0\n",
    "        sum_2 = 0\n",
    "        if len(odd_list)and len(even_card):\n",
    "            sum_1 = sum-odd_list[-1]+even_card[-1]\n",
    "        if len(even_list)and len(odd_card):\n",
    "            sum_2 = sum-even_list[-1]+odd_card[-1]\n",
    "        if sum_1%2 and sum_2%2:\n",
    "            return 0\n",
    "        \n",
    "        if sum_1>sum_2:\n",
    "            return sum_1\n",
    "        else:\n",
    "            return sum_2\n",
    "\n",
    "\n",
    "\n",
    "           \n",
    "                \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort() \n",
    "        odd_list = []\n",
    "        even_list = []\n",
    "        sum = 0\n",
    "        for i in range(cnt):\n",
    "            sum=cards[-1]+sum\n",
    "            if cards[-1]%2==0:\n",
    "                odd_list.append(cards[-1])\n",
    "            else:\n",
    "                even_list.append(cards[-1])\n",
    "            cards.pop()\n",
    "            \n",
    "        if sum%2==0:\n",
    "            return sum\n",
    "\n",
    "        odd_card = []\n",
    "        even_card = []\n",
    "        for i in cards:\n",
    "            if i%2==0:\n",
    "                odd_card.append(i)\n",
    "            else:\n",
    "                even_card.append(i)\n",
    "        \n",
    "        sum_1 = 0\n",
    "        sum_2 = 0\n",
    "        if len(odd_list)and len(even_card):\n",
    "            sum_1 = sum-odd_list[-1]+even_card[-1]\n",
    "        if len(even_list)and len(odd_card):\n",
    "            sum_2 = sum-even_list[-1]+odd_card[-1]\n",
    "        if sum_1%2 and sum_2%2:\n",
    "            return 0\n",
    "        \n",
    "        if sum_1>sum_2:\n",
    "            return sum_1\n",
    "        else:\n",
    "            return sum_2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "           \n",
    "                \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort() \n",
    "        odd_list = []\n",
    "        even_list = []\n",
    "        sum = 0\n",
    "        for i in range(cnt):\n",
    "            sum=cards[-1]+sum\n",
    "            if cards[-1]%2==0:\n",
    "                odd_list.append(cards[-1])\n",
    "            else:\n",
    "                even_list.append(cards[-1])\n",
    "            cards.pop()\n",
    "            \n",
    "        if sum%2==0:\n",
    "            return sum\n",
    "\n",
    "        odd_card = []\n",
    "        even_card = []\n",
    "        for i in cards:\n",
    "            if i%2==0:\n",
    "                odd_card.append(i)\n",
    "            else:\n",
    "                even_card.append(i)\n",
    "        \n",
    "        sum_1 = 0\n",
    "        sum_2 = 0\n",
    "        if len(odd_list)and len(even_card):\n",
    "            sum_1 = sum-odd_list[-1]+even_card[-1]\n",
    "        if len(even_list)and len(odd_card):\n",
    "            sum_2 = sum-even_list[-1]+odd_card[-1]\n",
    "        \n",
    "        if sum_1>sum_2:\n",
    "            return sum_1\n",
    "        else:\n",
    "            return sum_2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "           \n",
    "                \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        ou_sum=[]\n",
    "        ji_sum=[]\n",
    "        sum=0\n",
    "        for i in range(cnt):\n",
    "            sum=cards[-1]+sum\n",
    "            if cards[-1]%2==0:\n",
    "                ou_sum.append(cards[-1])\n",
    "            else:\n",
    "                ji_sum.append(cards[-1])\n",
    "            cards.pop()\n",
    "\n",
    "        if sum%2==0:\n",
    "            return sum\n",
    "\n",
    "        ou_cards=[]\n",
    "        ji_cards=[]\n",
    "        for i in cards:\n",
    "            if i%2==0:\n",
    "                ou_cards.append(i)\n",
    "            else:\n",
    "                ji_cards.append(i)\n",
    "\n",
    "        sum_1=0\n",
    "        sum_2=0\n",
    "        if len(ou_sum)and len(ji_cards):\n",
    "            sum_1=sum-ou_sum[-1]+ji_cards[-1]\n",
    "        if len(ji_sum)and len(ou_cards):\n",
    "            sum_2=sum-ji_sum[-1]+ou_cards[-1]\n",
    "        sum=sum_1 if sum_1>sum_2 else sum_2\n",
    "        return sum\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "           \n",
    "                \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        n = len(cards)\n",
    "        cards.sort()\n",
    "        odds = evens= -1\n",
    "        i = n-1\n",
    "        sum = 0\n",
    "        while i >= n - cnt:\n",
    "            sum += cards[i]\n",
    "            if cards[i] & 1 == 0:\n",
    "                evens = cards[i]\n",
    "            else:\n",
    "                odds = cards[i]\n",
    "            i -= 1\n",
    "        if sum & 1 == 0:\n",
    "            print(\"hello\")\n",
    "            return sum\n",
    "        res = 0\n",
    "        print(sum,odds)\n",
    "        while i >= 0:\n",
    "            if cards[i] & 1 == 0 and odds != -1:\n",
    "                res = max(res,sum + cards[i] - odds)\n",
    "            if cards[i] & 1 == 1 and evens != -1:\n",
    "                res = max(res,sum + cards[i] - evens)\n",
    "            i -= 1\n",
    "        print(\"h\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my:排序 -- 101/104\n",
    "# class Solution:\n",
    "#     def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "#         cards=sorted(cards,reverse=True)\n",
    "#         k=cnt\n",
    "#         su=sum(cards[:k])\n",
    "#         if su%2==0:\n",
    "#             return su \n",
    "#         else:\n",
    "#             su-=cards[k-1]\n",
    "#             for i in range(k,len(cards)):\n",
    "#                 if (cards[i]+cards[k-1])%2==1:\n",
    "#                     return su+cards[i]\n",
    "#             return 0\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards=sorted(cards,reverse=True)\n",
    "        k=cnt\n",
    "        su=sum(cards[:k])\n",
    "        if su%2==0:\n",
    "            return su\n",
    "        else:\n",
    "            # su-=cards[k-1]\n",
    "            # a,b=su-cards[k-1],\n",
    "            # for i in range(k,len(cards)):\n",
    "            #     if (cards[i]+cards[k-1])%2==1:\n",
    "            #         return su+cards[i]\n",
    "            # return -1\n",
    "            ans=0\n",
    "            for j in range(k-1,-1,-1):\n",
    "                tmp=su\n",
    "                for i in range(k,len(cards)):\n",
    "                    if (cards[i]+cards[j])%2==1:\n",
    "                        ans=max(ans,tmp-cards[j]+cards[i])\n",
    "                        break\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        n = len(cards)\n",
    "        s = 0\n",
    "        mn_even = mn_odd = inf\n",
    "        for i in range(n - 1, n - cnt - 1, -1):\n",
    "            s += cards[i]\n",
    "            if cards[i] % 2:\n",
    "                mn_odd = cards[i]\n",
    "            else:\n",
    "                mn_even = cards[i]\n",
    "        if s % 2 == 0:\n",
    "            return s\n",
    "        ans = 0\n",
    "        for i in range(n - cnt - 1, -1 , -1):\n",
    "            if cards[i] % 2 and mn_even != inf:\n",
    "                ans = max(ans, s - mn_even + cards[i])\n",
    "                mn_even = inf\n",
    "            elif cards[i] % 2 == 0 and mn_odd != inf:\n",
    "                ans = max(ans, s - mn_odd + cards[i])\n",
    "                mn_odd = inf\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse = True)\n",
    "        min_arr = [0,0]\n",
    "        now_sum = 0\n",
    "\n",
    "        for i in range(cnt):\n",
    "            val = cards[i]\n",
    "            now_sum += val\n",
    "            min_arr[val & 1] = val\n",
    "\n",
    "        if now_sum & 1 == 0:\n",
    "            return now_sum\n",
    "\n",
    "        res = 0\n",
    "        for i in range(cnt, len(cards)):\n",
    "            val = cards[i]\n",
    "\n",
    "            op = (val % 2) ^ 1\n",
    "\n",
    "            if min_arr[op] != 0:\n",
    "                res = max (res, now_sum - min_arr[op] + val)\n",
    "\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        res = sum(cards[:cnt])\n",
    "        if res % 2 == 0: return res\n",
    "        else:\n",
    "            last_odd,last_even=-1,-1\n",
    "            for i in range(cnt):\n",
    "                if cards[i] % 2 == 0:\n",
    "                    last_even = cards[i]\n",
    "                else:\n",
    "                    last_odd = cards[i]\n",
    "            top_odd,top_even=-1,-1\n",
    "            for j in range(len(cards)-1,cnt-1,-1):\n",
    "                if cards[j] % 2 == 0:\n",
    "                    top_even = cards[j]\n",
    "                else:\n",
    "                    top_odd = cards[j]\n",
    "            ans=0\n",
    "            if last_even != -1 and top_odd != -1:\n",
    "                ans = res - last_even + top_odd\n",
    "            if last_odd != -1 and top_even != -1:\n",
    "                t = res - last_odd + top_even\n",
    "                if ans > 0:\n",
    "                    ans = max(ans, t) \n",
    "                else:\n",
    "                    ans = t\n",
    "            return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        q=sum(cards[-cnt:])\n",
    "        if q%2==0:\n",
    "            return q\n",
    "        lon=len(cards)\n",
    "        i=lon-cnt\n",
    "        q1=0\n",
    "        while i <lon:\n",
    "            if cards[i]%2==1:\n",
    "                e1=cards[i]\n",
    "                j=lon-cnt-1\n",
    "                while j>=0:\n",
    "                    if cards[j]%2==0:\n",
    "                        e2=cards[j]\n",
    "                        q1=q-cards[i]+cards[j]\n",
    "                        break\n",
    "                    j-=1\n",
    "                break\n",
    "            i+=1\n",
    "            \n",
    "        q2=0\n",
    "        i=lon-cnt\n",
    "        while i <lon:\n",
    "            if cards[i]%2==0:\n",
    "                e1=cards[i]\n",
    "                j=lon-cnt-1\n",
    "                while j>=0:\n",
    "                    if cards[j]%2==1:\n",
    "                        e2=cards[j]\n",
    "                        q2=q-cards[i]+cards[j]\n",
    "                        break\n",
    "                    j-=1\n",
    "                break\n",
    "            i+=1\n",
    "        \n",
    "        return max(q1,q2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        res = sum(cards[:cnt])\n",
    "        if res % 2 == 0:\n",
    "            return res\n",
    "        else:\n",
    "            last_odd,last_even=-1,-1\n",
    "            for i in range(cnt):\n",
    "                if cards[i] % 2 == 0:\n",
    "                    last_even = cards[i]\n",
    "                else:\n",
    "                    last_odd = cards[i]\n",
    "            top_odd,top_even=-1,-1\n",
    "            for j in range(len(cards)-1,cnt-1,-1):\n",
    "                if cards[j] % 2 == 0:\n",
    "                    top_even = cards[j]\n",
    "                else:\n",
    "                    top_odd = cards[j]\n",
    "            ans=0\n",
    "            if last_even != -1 and top_odd != -1:\n",
    "                ans = res - last_even + top_odd\n",
    "            if last_odd != -1 and top_even != -1:\n",
    "                t = res - last_odd + top_even\n",
    "                if ans > 0:\n",
    "                    ans = max(ans, t) \n",
    "                else:\n",
    "                    ans = t\n",
    "            return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        n = len(cards)\n",
    "        cards.sort(reverse = True)\n",
    "        count = sum(cards[:cnt])\n",
    "        ans = 0\n",
    "        if count % 2 ==0:\n",
    "            return count\n",
    "        \n",
    "        odd = [0]\n",
    "        even = [0]\n",
    "        for i in range(cnt):\n",
    "            if cards[i] % 2==1:\n",
    "                odd.append(odd[-1]+cards[i])\n",
    "            else:\n",
    "                even.append(even[-1]+cards[i])\n",
    "        finish = False\n",
    "        for i in range(cnt,n):\n",
    "            if len(even)>1 and cards[i] % 2 ==1:\n",
    "                ans = max(ans,even[-2]+odd[-1]+cards[i])\n",
    "            elif cards[i] % 2 == 0:\n",
    "                ans = max(ans,even[-1]+odd[-2]+cards[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        n=len(cards)\n",
    "        \n",
    "        A,B=cards[:n-cnt],cards[n-cnt:n]\n",
    "        Q=sum(B)\n",
    "        if Q%2==0:\n",
    "            return Q\n",
    "        if n==cnt :return 0\n",
    "        else:\n",
    "            z,x=0,0\n",
    "            g=30\n",
    "            for i in A[::-1]:\n",
    "                if (B[0]-i)%2!=0:\n",
    "                    z=Q-B[0]+i\n",
    "                    break\n",
    "        \n",
    "            for j in B:\n",
    "                if (j-B[0])%2!=0:\n",
    "                    x=Q-j+A[-1]\n",
    "                    break\n",
    "            \n",
    "            return max(x,z)\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        res = sum(cards[:cnt])\n",
    "        if res % 2 == 0:\n",
    "            return res\n",
    "        else:\n",
    "            last_odd,last_even=-1,-1\n",
    "            for i in range(cnt):\n",
    "                if cards[i] % 2 == 0:\n",
    "                    last_even = cards[i]\n",
    "                else:\n",
    "                    last_odd = cards[i]\n",
    "            top_odd,top_even=-1,-1\n",
    "            for j in range(len(cards)-1,cnt-1,-1):\n",
    "                if cards[j] % 2 == 0:\n",
    "                    top_even = cards[j]\n",
    "                else:\n",
    "                    top_odd = cards[j]\n",
    "            ans=0\n",
    "            if last_even != -1 and top_odd != -1:\n",
    "                ans = res - last_even + top_odd\n",
    "            if last_odd != -1 and top_even != -1:\n",
    "                t = res - last_odd + top_even\n",
    "                if ans > 0:\n",
    "                    ans = max(ans, t) \n",
    "                else:\n",
    "                    ans = t\n",
    "            return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        n = len(cards)\n",
    "        cards.sort(reverse = True)\n",
    "        count = sum(cards[:cnt])\n",
    "        ans = 0\n",
    "        if count % 2 ==0:\n",
    "            return count\n",
    "        \n",
    "        select = [0,0]\n",
    "        finish = False\n",
    "        for i in range(cnt,n):\n",
    "            if cards[i] % 2 == 1 and select[0] == 0:\n",
    "                select[0] = cards[i]\n",
    "                if not finish:\n",
    "                    finish = True\n",
    "                else:\n",
    "                    break\n",
    "            if cards[i] % 2 == 0 and select[1] == 0:\n",
    "                select[1] = cards[i]\n",
    "                if not finish:\n",
    "                    finish = True\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        a = cards[cnt-1] % 2\n",
    "        if select[a] !=0:\n",
    "            ans = count-cards[cnt-1]+ select[a]\n",
    "        if cnt>1:\n",
    "            for i in range(cnt-2,-1,-1):\n",
    "                if cards[i] % 2 !=a:\n",
    "                    if select[1-a] !=0:\n",
    "                        ans = max(ans,count-cards[i]+ select[1-a])\n",
    "                    break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "\n",
    "        cards.sort(reverse = True)\n",
    "        rst = sum(cards[:cnt])\n",
    "\n",
    "        if rst % 2 == 0:\n",
    "            return rst\n",
    "\n",
    "        fst_even = None; fst_odd = None\n",
    "        for i in range(cnt - 1, -1, -1):\n",
    "            if fst_even and fst_odd:\n",
    "                break\n",
    "\n",
    "            if fst_even is None and cards[i] % 2 == 0:\n",
    "                fst_even = cards[i]\n",
    "\n",
    "            if fst_odd is None and cards[i] % 2 == 1:\n",
    "                fst_odd = cards[i]\n",
    "\n",
    "        left_even = None; left_odd = None\n",
    "        for i in range(cnt, len(cards)):\n",
    "            if left_even and left_odd:\n",
    "                break\n",
    "\n",
    "            if left_even is None and cards[i] % 2 == 0:\n",
    "                left_even = cards[i]\n",
    "\n",
    "            if left_odd is None and cards[i] % 2 == 1:\n",
    "                left_odd = cards[i]\n",
    "\n",
    "        rst1 = 0\n",
    "        if fst_even and left_odd:\n",
    "            rst1 = rst - fst_even + left_odd\n",
    "\n",
    "        rst2 = 0\n",
    "        if fst_odd and left_even:\n",
    "            rst2 = rst - fst_odd + left_even\n",
    "\n",
    "        return max(rst1, rst2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse = True)\n",
    "        res = sum(cards[:cnt])\n",
    "        if res % 2 == 0:\n",
    "            return res\n",
    "        else:\n",
    "            las_odd,las_even = -1,-1\n",
    "            for i in range(cnt):\n",
    "                if cards[i] % 2 == 0:\n",
    "                    las_even = cards[i]\n",
    "                else:\n",
    "                    las_odd = cards[i]\n",
    "            \n",
    "            fir_odd,fir_even = -1,-1\n",
    "            for i in range(len(cards)-1,cnt-1,-1):\n",
    "                if cards[i] % 2 == 0:\n",
    "                    fir_even = cards[i]\n",
    "                else:\n",
    "                    fir_odd = cards[i]\n",
    "            \n",
    "            ans = 0\n",
    "            temp = 0\n",
    "            if las_even != -1 and fir_odd != -1:\n",
    "                ans = res - las_even + fir_odd\n",
    "            if las_odd != -1 and fir_even != -1:\n",
    "                temp = res - las_odd + fir_even\n",
    "            ans = max(ans,temp)\n",
    "            \n",
    "            return ans\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse = True)\n",
    "        total = sum(cards[:cnt])\n",
    "        if total % 2 == 0:\n",
    "            return total\n",
    "        #减去一个偶数，再加入一个奇数\n",
    "        #或减去一个奇数，再加入一个偶数\n",
    "        def findNum(lst,odd = True):\n",
    "            if odd:\n",
    "                for num in lst:\n",
    "                    if num % 2 != 0:\n",
    "                        return num\n",
    "            else:\n",
    "                for num in lst:\n",
    "                    if num % 2 == 0:\n",
    "                        return num\n",
    "            return None\n",
    "        ans = 0\n",
    "        odd_add = findNum(cards[cnt:],odd = True)\n",
    "        even_remove = findNum(cards[(cnt - 1)::-1],odd = False)\n",
    "        if odd_add and even_remove:\n",
    "            ans = total + odd_add - even_remove\n",
    "\n",
    "        even_add = findNum(cards[cnt:],odd = False)\n",
    "        odd_remove = findNum(cards[(cnt - 1)::-1],odd = True)\n",
    "        if even_add and odd_remove:\n",
    "            ans = max(ans,total + even_add - odd_remove)\n",
    "        \n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse = True)\n",
    "        ret = sum(cards[:cnt])\n",
    "        #print(f\"ret {ret}\")\n",
    "        if 0 == ret % 2:\n",
    "            return ret\n",
    "        else:\n",
    "            o, e = 0, 0\n",
    "            for i in range(cnt -1, -1, -1):\n",
    "                v = cards[i]\n",
    "                if 1 == v % 2:\n",
    "                    if 0 == o:\n",
    "                        o = v\n",
    "                else:\n",
    "                    if 0 == e:\n",
    "                        e = v\n",
    "                if o != 0 and e != 0:\n",
    "                    break\n",
    "            o1, e1 = 0, 0\n",
    "            for i in range(cnt, len(cards)):\n",
    "                v = cards[i]\n",
    "                if 1 == v % 2:\n",
    "                    if 0 == o1:\n",
    "                        o1 = v\n",
    "                else:\n",
    "                    if 0 == e1:\n",
    "                        e1 = v\n",
    "                if o1 != 0 and e1 != 0:\n",
    "                    break\n",
    "            d = 0\n",
    "            if e != 0 and o1 != 0:\n",
    "                d = e - o1\n",
    "            d1 = 0\n",
    "            if o != 0 and e1 != 0:\n",
    "                d1 = o - e1\n",
    "            if 0 == d and 0 == d1:\n",
    "                return 0\n",
    "            elif d1 != 0 and d != 0:\n",
    "                return ret - min(d1, d)\n",
    "            elif d1 != 0:\n",
    "                return ret - d1\n",
    "            else:\n",
    "                return ret - d\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        arr = [0, 0]\n",
    "        top_sum = 0\n",
    "\n",
    "        # 累加前 cnt 个数字的值\n",
    "        # 并得到前 cnt 个数字中最小的 「奇 / 偶」 数\n",
    "        for i in range(cnt):\n",
    "            val = cards[i]\n",
    "            top_sum += val\n",
    "            arr[val & 1] = val\n",
    "        # 如果前 cnt 个数已经是偶数，则返回\n",
    "        if (top_sum & 1) == 0:\n",
    "            return top_sum\n",
    "\n",
    "        res = 0\n",
    "        # 用后面较大的 「奇 / 偶」 数 来替换 top_sum 中最小的 「偶 / 奇」 数\n",
    "        # 来更新最佳答案\n",
    "        for i in range(cnt, len(cards)):\n",
    "            val = cards[i]\n",
    "            # val = 1 时 op = 0   val = 0 时 op = 1\n",
    "            opposite = val & 1 ^ 1\n",
    "            # top_sum 中没有对应属性的数字则不替换\n",
    "            if arr[opposite] != 0:\n",
    "                res = max(res, top_sum - arr[opposite] + val)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        # 排序并取最大的cnt张求和\n",
    "        cards.sort()\n",
    "        sm = sum(cards[-cnt:])\n",
    "\n",
    "        if sm & 1:\n",
    "            # m1和m2为已选牌中最小的奇数和偶数，直接暴力枚举即可\n",
    "            m1 = min((x for x in cards[-cnt:] if x & 1), default = 0)\n",
    "            m2 = min((x for x in cards[-cnt:] if not (x & 1)), default = 0)\n",
    "            # ma为当前最大和，直接暴力枚举，不考虑已知最优解可以返回的情况\n",
    "            ma = 0\n",
    "            for x in cards[-cnt-1::-1]:\n",
    "                # 这样在此处就简化为2种情况：x为奇数且m2存在，或者x为偶数且m1存在\n",
    "                if (x & 1) and m2:\n",
    "                    ma = max(ma, sm - m2 + x)\n",
    "                elif not (x & 1) and m1:\n",
    "                    ma = max(ma, sm - m1 + x)\n",
    "            return ma\n",
    "        else:\n",
    "            return sm\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        n = len(cards)\n",
    "        cards.sort()\n",
    "        odds = evens= -1\n",
    "        i = n-1\n",
    "        sum = 0\n",
    "        while i >= n - cnt:\n",
    "            sum += cards[i]\n",
    "            if cards[i] & 1 == 0:\n",
    "                evens = cards[i]\n",
    "            else:\n",
    "                odds = cards[i]\n",
    "            i -= 1\n",
    "        if sum & 1 == 0:\n",
    "            return sum\n",
    "        res = 0\n",
    "        while i >= 0:\n",
    "            if cards[i] & 1 == 0 and odds != -1:\n",
    "                res = max(res,sum + cards[i] - odds)\n",
    "            if cards[i] & 1 == 1 and evens != -1:\n",
    "                res = max(res,sum + cards[i] - evens)\n",
    "            i -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "       cards.sort(reverse=True)\n",
    "       sums, ans = sum(cards[:cnt]), 0\n",
    "       if sums % 2 == 0:\n",
    "           return sums\n",
    "\n",
    "       def replace(num):\n",
    "           nonlocal ans\n",
    "           for k, v in enumerate(cards[cnt:]):\n",
    "               if v % 2 != num % 2:\n",
    "                   ans = max(ans, sums-num+v)\n",
    "                   return\n",
    "                   \n",
    "       replace(cards[cnt - 1])\n",
    "       for i in range(cnt-2, -1,-1):\n",
    "           if cards[i] % 2 != cards[cnt-1] % 2:\n",
    "               replace(cards[i]) \n",
    "               break\n",
    "       return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse = True)\n",
    "        ret = sum(cards[:cnt])\n",
    "        #print(f\"ret {ret}\")\n",
    "        if 0 == ret % 2:\n",
    "            return ret\n",
    "        else:\n",
    "            o, e = 0, 0\n",
    "            for i in range(cnt -1, -1, -1):\n",
    "                v = cards[i]\n",
    "                if 1 == v % 2:\n",
    "                    if 0 == o:\n",
    "                        o = v\n",
    "                else:\n",
    "                    if 0 == e:\n",
    "                        e = v\n",
    "                if o != 0 and e != 0:\n",
    "                    break\n",
    "            o1, e1 = 0, 0\n",
    "            for i in range(cnt, len(cards)):\n",
    "                v = cards[i]\n",
    "                if 1 == v % 2:\n",
    "                    if 0 == o1:\n",
    "                        o1 = v\n",
    "                else:\n",
    "                    if 0 == e1:\n",
    "                        e1 = v\n",
    "                if o1 != 0 and e1 != 0:\n",
    "                    break\n",
    "            d = 0\n",
    "            if e != 0 and o1 != 0:\n",
    "                d = e - o1\n",
    "            d1 = 0\n",
    "            if o != 0 and e1 != 0:\n",
    "                d1 = o - e1\n",
    "            if 0 == d and 0 == d1:\n",
    "                return 0\n",
    "            elif d1 != 0 and d != 0:\n",
    "                return ret - min(d1, d)\n",
    "            elif d1 != 0:\n",
    "                return ret - d1\n",
    "            else:\n",
    "                return ret - d\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int,count=0) -> int:\n",
    "        count=0\n",
    "        i,j=0,0\n",
    "        cards.sort()\n",
    "        cards.reverse()\n",
    "        even=[num for num in cards if num%2==0]\n",
    "        odd=[num for num in cards if num%2==1]\n",
    "        if cnt%2==1:\n",
    "            if len(even)>0:\n",
    "                count+=even[i]\n",
    "                cnt-=1\n",
    "                i+=1\n",
    "            else:\n",
    "                return 0\n",
    "        while cnt>0:\n",
    "            if len(even)>=i+2 and len(odd)>=j+2:\n",
    "                if even[i]+even[i+1]>odd[j]+odd[j+1]:\n",
    "                    count+=(even[i]+even[i+1])\n",
    "                    i+=2\n",
    "                else:\n",
    "                    count+=(odd[j]+odd[j+1])\n",
    "                    j+=2\n",
    "            elif len(even)>=i+2:\n",
    "                count += (even[i] + even[i+1])\n",
    "                i+=2\n",
    "            elif len(odd)>=j+2:\n",
    "                count+=(odd[j]+odd[j+1])\n",
    "                j+=2\n",
    "            else:\n",
    "                return 0\n",
    "            cnt-=2\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "       cards.sort(reverse=True)\n",
    "       sums, ans = sum(cards[:cnt]), 0\n",
    "       if sums % 2 == 0:\n",
    "           return sums\n",
    "\n",
    "       def replace(num):\n",
    "           nonlocal ans\n",
    "           for k, v in enumerate(cards[cnt:]):\n",
    "               if v % 2 != num % 2:\n",
    "                   ans = max(ans, sums-num+v)\n",
    "                   return\n",
    "                   \n",
    "       replace(cards[cnt - 1])\n",
    "       for i in range(cnt-2, -1,-1):\n",
    "           if cards[i] % 2 != cards[cnt-1] % 2:\n",
    "               replace(cards[i]) \n",
    "               break\n",
    "       return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my:排序 -- 101/104\n",
    "# class Solution:\n",
    "#     def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "#         cards=sorted(cards,reverse=True)\n",
    "#         k=cnt\n",
    "#         su=sum(cards[:k])\n",
    "#         if su%2==0:\n",
    "#             return su \n",
    "#         else:\n",
    "#             su-=cards[k-1]\n",
    "#             for i in range(k,len(cards)):\n",
    "#                 if (cards[i]+cards[k-1])%2==1:\n",
    "#                     return su+cards[i]\n",
    "#             return 0\n",
    "\n",
    "# ### my：排序--v2--pass\n",
    "# class Solution:\n",
    "#     def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "#         cards=sorted(cards,reverse=True)\n",
    "#         k=cnt\n",
    "#         su=sum(cards[:k])\n",
    "#         if su%2==0:\n",
    "#             return su\n",
    "#         else:\n",
    "#             # su-=cards[k-1]\n",
    "#             # a,b=su-cards[k-1],\n",
    "#             # for i in range(k,len(cards)):\n",
    "#             #     if (cards[i]+cards[k-1])%2==1:\n",
    "#             #         return su+cards[i]\n",
    "#             # return -1\n",
    "#             ans=0\n",
    "#             for j in range(k-1,-1,-1):\n",
    "#                 tmp=su\n",
    "#                 for i in range(k,len(cards)):\n",
    "#                     if (cards[i]+cards[j])%2==1:\n",
    "#                         ans=max(ans,tmp-cards[j]+cards[i])\n",
    "#                         break\n",
    "#             return ans\n",
    "\n",
    "### 网：\n",
    "class Solution:\n",
    "   def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "       cards.sort(reverse=True)\n",
    "       sums, ans = sum(cards[:cnt]), 0\n",
    "       if sums % 2 == 0:\n",
    "           return sums\n",
    "\n",
    "       def replace(num):\n",
    "           nonlocal ans\n",
    "           for k, v in enumerate(cards[cnt:]):\n",
    "               if v % 2 != num % 2:\n",
    "                   ans = max(ans, sums-num+v)\n",
    "                   return\n",
    "                   \n",
    "       replace(cards[cnt - 1])\n",
    "       for i in range(cnt-2, -1,-1):\n",
    "           if cards[i] % 2 != cards[cnt-1] % 2:\n",
    "               replace(cards[i]) \n",
    "               break\n",
    "       return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        sums, ans = sum(cards[:cnt]), 0\n",
    "        if sums & 1 == 0:\n",
    "            return sums\n",
    "\n",
    "        def replace(num):\n",
    "            nonlocal ans\n",
    "            for k, v in enumerate(cards[cnt:]):\n",
    "                if v & 1 != num & 1:\n",
    "                    ans = max(ans, sums-num+v)\n",
    "                    return\n",
    "                    \n",
    "        replace(cards[cnt - 1])\n",
    "        for i in range(cnt-2, -1,-1):\n",
    "            if cards[i] & 1 != cards[cnt-1] & 1:\n",
    "                replace(cards[i]) \n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "       cards.sort(reverse=True)\n",
    "       sums, ans = sum(cards[:cnt]), 0\n",
    "       if sums % 2 == 0:\n",
    "           return sums\n",
    "\n",
    "       def replace(num):\n",
    "           nonlocal ans\n",
    "           for k, v in enumerate(cards[cnt:]):\n",
    "               if v % 2 != num % 2:\n",
    "                   ans = max(ans, sums-num+v)\n",
    "                   return\n",
    "                   \n",
    "       replace(cards[cnt - 1])\n",
    "       for i in range(cnt-2, -1,-1):\n",
    "           if cards[i] % 2 != cards[cnt-1] % 2:\n",
    "               replace(cards[i]) \n",
    "               break\n",
    "       return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        if cnt == len(cards):\n",
    "            if sum(cards) % 2 == 0:\n",
    "                return sum(cards)\n",
    "            else:\n",
    "                return 0\n",
    "        cards.sort(reverse=True)\n",
    "        res = 0\n",
    "        latest_odd = -1\n",
    "        latest_even = -1\n",
    "        for i in range(cnt):\n",
    "            res += cards[i]\n",
    "            if cards[i] % 2 == 0:\n",
    "                latest_even = cards[i]\n",
    "            else:\n",
    "                latest_odd = cards[i]\n",
    "        if res % 2 == 0:\n",
    "            return res\n",
    "        max_odd_res = -1 * 10 ** 5\n",
    "        max_even_res = -1 * 10 ** 5\n",
    "        for i in range(cnt, len(cards)):\n",
    "            if cards[i] % 2 == 0:\n",
    "                max_even_res = max(max_even_res, cards[i])\n",
    "            else:\n",
    "                max_odd_res = max(max_odd_res, cards[i])\n",
    "        if latest_odd > 0 and latest_even > 0:\n",
    "            diff = min(latest_odd - max_even_res, latest_even - max_odd_res)\n",
    "            return res - diff\n",
    "        elif latest_odd > 0:\n",
    "            if max_even_res < 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return res - (latest_odd - max_even_res)\n",
    "        else:\n",
    "            if max_odd_res < 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return res - (latest_even - max_odd_res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int,count=0) -> int:\n",
    "        count=0\n",
    "        i,j=0,0\n",
    "        cards.sort()\n",
    "        cards.reverse()\n",
    "        even=[num for num in cards if num%2==0]\n",
    "        odd=[num for num in cards if num%2==1]\n",
    "        if cnt%2==1:\n",
    "            if len(even)>0:\n",
    "                count+=even[i]\n",
    "                cnt-=1\n",
    "                i+=1\n",
    "            else:\n",
    "                return 0\n",
    "        while cnt>0:\n",
    "            if len(even)>=i+2 and len(odd)>=j+2:\n",
    "                if even[i]+even[i+1]>odd[j]+odd[j+1]:\n",
    "                    count+=(even[i]+even[i+1])\n",
    "                    i+=2\n",
    "                else:\n",
    "                    count+=(odd[j]+odd[j+1])\n",
    "                    j+=2\n",
    "            elif len(even)>=i+2:\n",
    "                count += (even[i] + even[i+1])\n",
    "                i+=2\n",
    "            elif len(odd)>=j+2:\n",
    "                count+=(odd[j]+odd[j+1])\n",
    "                j+=2\n",
    "            else:\n",
    "                return 0\n",
    "            cnt-=2\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        selected = []\n",
    "        max_odd_out, max_even_out = float('-inf'), float('-inf')        \n",
    "        for c in cards:\n",
    "            if len(selected) == cnt and selected[0] < c:\n",
    "                c = heappushpop(selected, c)\n",
    "                \n",
    "            if len(selected) < cnt:\n",
    "                heappush(selected, c)\n",
    "            elif c % 2 == 0:\n",
    "                max_even_out = max(max_even_out, c)\n",
    "            else:\n",
    "                max_odd_out = max(max_odd_out, c)\n",
    "        \n",
    "        odd_cnt = 0\n",
    "        min_odd_in, min_even_in = float('inf'), float('inf')\n",
    "        for c in selected:\n",
    "            if c % 2 == 1:\n",
    "                odd_cnt += 1\n",
    "                min_odd_in = min(min_odd_in, c)\n",
    "            else:\n",
    "                min_even_in = min(min_even_in, c)\n",
    "\n",
    "\n",
    "        ans = sum(selected)\n",
    "        if odd_cnt % 2 == 1:\n",
    "            ans += max(max_even_out - min_odd_in, max_odd_out - min_even_in)\n",
    "\n",
    "        # print(selected, max_odd_out, max_even_out, min_even_in, min_odd_in, odd_cnt)\n",
    "        return 0 if ans == float('-inf') else ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        n = len(cards)\n",
    "        cards.sort()\n",
    "        selectd = cards[n-cnt:]\n",
    "        ans = sum(selectd)\n",
    "        m = sum(1 for c in selectd if c % 2 == 1)\n",
    "\n",
    "        \n",
    "\n",
    "        if m % 2 == 1:\n",
    "            a = -min (c for c in selectd if c % 2 == 1) + max((c for c in cards[:n-cnt] if c % 2 == 0), default=float('-inf'))\n",
    "            b = -min ((c for c in selectd if c % 2 == 0), default=float('inf')) + max((c for c in cards[:n-cnt] if c % 2 == 1), default=float('-inf'))\n",
    "            ans += max(a,b)\n",
    "        return 0 if ans == float('-inf') else ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        sm = sum(cards[-cnt:])\n",
    "        m1 = min((x for x in cards[-cnt:] if x & 1), default = 0)\n",
    "        m2 = min((x for x in cards[-cnt:] if not (x & 1)), default = 0)\n",
    "        ma = 0\n",
    "        if sm & 1:\n",
    "            if cnt >= len(cards): return 0\n",
    "            for x in cards[-cnt-1::-1]:\n",
    "                if (x & 1) and m2:\n",
    "                    ma = max(ma, sm - m2 + x)\n",
    "                elif not (x & 1) and m1:\n",
    "                    ma = max(ma, sm - m1 + x)\n",
    "                # if (x & 1) != (cards[-cnt] & 1):\n",
    "                #     return sm - cards[-cnt] + x\n",
    "            return ma\n",
    "        else:\n",
    "            return sm\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int,count=0) -> int:\n",
    "        count=0\n",
    "        i,j=0,0\n",
    "        cards.sort(reverse=True)\n",
    "        even=[num for num in cards if num%2==0]\n",
    "        odd=[num for num in cards if num%2==1]\n",
    "        if cnt%2==1:\n",
    "            if len(even)>0:\n",
    "                count+=even[i]\n",
    "                cnt-=1\n",
    "                i+=1\n",
    "            else:\n",
    "                return 0\n",
    "        while cnt>0:\n",
    "            if len(even)>=i+2 and len(odd)>=j+2:\n",
    "                if even[i]+even[i+1]>odd[j]+odd[j+1]:\n",
    "                    count+=(even[i]+even[i+1])\n",
    "                    i+=2\n",
    "                else:\n",
    "                    count+=(odd[j]+odd[j+1])\n",
    "                    j+=2\n",
    "            elif len(even)>=i+2:\n",
    "                count += (even[i] + even[i+1])\n",
    "                i+=2\n",
    "            elif len(odd)>=j+2:\n",
    "                count+=(odd[j]+odd[j+1])\n",
    "                j+=2\n",
    "            else:\n",
    "                return 0\n",
    "            cnt-=2\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        # 数组从大到小排序\n",
    "        cards.sort(reverse=True)\n",
    "        # 先选择cards中最大的cnt项\n",
    "        chosen = cards[:cnt]\n",
    "        # 如果chosen总和恰好为偶数, 直接返回\n",
    "        if sum(chosen) % 2 == 0:\n",
    "            return sum(chosen)\n",
    "\n",
    "        # 如果不为偶数,那么\n",
    "        # 分两种情况讨论：\n",
    "        p1 = p2 = 0\n",
    "        # 情况1:替换 card[cnt−1]；\n",
    "        a = chosen[-1]\n",
    "        b = [i for i in cards[cnt:] if (a+i)%2 != 0]\n",
    "        if b:\n",
    "            p1 = sum(chosen) - a + b[0]\n",
    "\n",
    "        # 情况2:替换前 cnt个元素中，最小的且奇偶性和 card[cnt−1]不同的元素。\n",
    "        for x in chosen[::-1]:\n",
    "            if x > a and (x+a) % 2 != 0:\n",
    "                for y in cards[cnt:]:\n",
    "                    if (x+y) % 2 != 0:\n",
    "                        p2 = sum(chosen) - x + y\n",
    "                        return max(p1, p2)\n",
    "        return max(p1, p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "\n",
    "        odd = sys.maxsize\n",
    "        even = sys.maxsize\n",
    "        sum = 0\n",
    "        cards.sort()\n",
    "        i = len(cards) - 1\n",
    "        while i >= len(cards)-cnt:\n",
    "            if cards[i] % 2 == 0:\n",
    "                even = cards[i]\n",
    "            else:\n",
    "                odd = cards[i]\n",
    "\n",
    "            sum += cards[i]\n",
    "            i -= 1\n",
    "\n",
    "        if sum % 2 == 0:\n",
    "            return sum\n",
    "\n",
    "        max_val = 0\n",
    "        oddFlag = False\n",
    "        evenFlag = False\n",
    "        evenNotExist = even == sys.maxsize\n",
    "        o2e = odd < even\n",
    "\n",
    "        i = len(cards) - cnt - 1\n",
    "        while i >= 0:\n",
    "            if not oddFlag and cards[i] % 2 == 0:\n",
    "                max_val = max(max_val, sum + cards[i] - odd)\n",
    "                oddFlag = True\n",
    "                if evenFlag or not o2e or evenNotExist:\n",
    "                    break\n",
    "            elif not evenFlag and cards[i] % 2 == 1 and not evenNotExist:\n",
    "                max_val = max(max_val, sum + cards[i] - even)\n",
    "                evenFlag = True\n",
    "                if oddFlag or o2e:\n",
    "                    break\n",
    "            i -= 1\n",
    "\n",
    "        return max_val           \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        # 数组从大到小排序\n",
    "        cards.sort(reverse=True)\n",
    "        # 先选择cards中最大的cnt项\n",
    "        chosen = cards[:cnt]\n",
    "        # 如果chosen总和恰好为偶数, 直接返回\n",
    "        if sum(chosen) % 2 == 0:\n",
    "            return sum(chosen)\n",
    "\n",
    "        # 如果不为偶数,那么\n",
    "        # 分两种情况讨论：\n",
    "        # 替换 card[cnt−1]；\n",
    "        # 替换前 cnt个元素中，最小的且奇偶性和 card[cnt−1]不同的元素。\n",
    "        p1 = p2 = 0\n",
    "        # 情况1:\n",
    "        a = chosen[-1]\n",
    "        for b in cards[cnt:]:\n",
    "            if (a+b) % 2 != 0:\n",
    "                p1 = sum(chosen) - a + b\n",
    "                break\n",
    "        # 情况2:\n",
    "        for x in chosen[::-1]:\n",
    "            if x != a and (x+a) % 2 != 0:\n",
    "                for y in cards[cnt:]:\n",
    "                    if (x+y) % 2 != 0:\n",
    "                        p2 = sum(chosen) - x + y\n",
    "                        return max(p1, p2)\n",
    "        return max(p1, p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        selected = []\n",
    "        max_odd_out, max_even_out = float('-inf'), float('-inf')        \n",
    "        for c in cards:\n",
    "            if len(selected) == cnt and selected[0] < c:\n",
    "                c = heappushpop(selected, c)\n",
    "                \n",
    "            if len(selected) < cnt:\n",
    "                heappush(selected, c)\n",
    "            elif c % 2 == 0:\n",
    "                max_even_out = max(max_even_out, c)\n",
    "            else:\n",
    "                max_odd_out = max(max_odd_out, c)\n",
    "        \n",
    "\n",
    "        min_odd_in = min((c for c in selected if c % 2 == 1), default=float('inf'))\n",
    "        min_even_in = min((c for c in selected if c % 2 == 0), default=float('inf'))\n",
    "        odd_count = sum(c for c in selected if c % 2 == 1)\n",
    "        ans = sum(selected)\n",
    "        if odd_count % 2 == 1:\n",
    "            ans += max(max_even_out - min_odd_in, max_odd_out - min_even_in)\n",
    "\n",
    "        # print(selected, max_odd_out, max_even_out, min_even_in, min_odd_in, odd_count)\n",
    "        return 0 if ans == float('-inf') else ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        last = cards[-cnt:]\n",
    "        sum_num = sum(last)\n",
    "        print(last)\n",
    "        print(sum_num)\n",
    "        odd,even = -1,-1\n",
    "        for i in last:\n",
    "            if i % 2 == 0 and even < 0:\n",
    "                even = i\n",
    "        \n",
    "            if i % 2 == 1 and odd < 0:\n",
    "                odd = i\n",
    "        if sum_num % 2 == 0:\n",
    "            return sum_num\n",
    "        print(even,odd)\n",
    "        res_max = 0\n",
    "\n",
    "        for i in cards[:-cnt][::-1]:\n",
    "            if i % 2 == 0 and odd >= 0:\n",
    "                res_max = max(res_max,sum_num-odd+i)\n",
    "            if i % 2 == 1 and even >= 0:\n",
    "                res_max = max(res_max,sum_num-even+i)\n",
    "        return res_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        last = cards[-cnt:]\n",
    "        sum_num = sum(last)\n",
    "        print(last)\n",
    "        print(sum_num)\n",
    "        odd,even = -1,-1\n",
    "        for i in last:\n",
    "            if i % 2 == 0 and even < 0:\n",
    "                even = i\n",
    "            else:\n",
    "                if i % 2 == 1 and odd < 0:\n",
    "                    odd = i\n",
    "        if sum_num % 2 == 0:\n",
    "            return sum_num\n",
    "        print(even,odd)\n",
    "        res_max = 0\n",
    "\n",
    "        for i in cards[:-cnt][::-1]:\n",
    "            if i % 2 == 0 and odd >= 0:\n",
    "                res_max = max(res_max,sum_num-odd+i)\n",
    "            if i % 2 == 1 and even >= 0:\n",
    "                res_max = max(res_max,sum_num-even+i)\n",
    "        return res_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        if cnt == 1:\n",
    "            maxo = 0\n",
    "            for i in cards:\n",
    "                if i % 2 == 0 and i > maxo:\n",
    "                    maxo = i\n",
    "            return maxo\n",
    "        cards.sort(reverse = True)\n",
    "        score = sum(cards[:cnt])\n",
    "        if score % 2 != 0 and len(cards) - cnt >= 1:\n",
    "            maxj = -1\n",
    "            maxo = -1\n",
    "            for i in range(cnt-1,-1,-1): # 找到前cnt个数中最小的奇数和偶数\n",
    "                if cards[i] % 2 == 0 and maxo == -1:\n",
    "                    maxo = cards[i]\n",
    "                if cards[i] % 2 != 0 and maxj == -1:\n",
    "                    maxj = cards[i]\n",
    "                if maxj != -1 and maxo != -1:\n",
    "                    break\n",
    "            minj = -1\n",
    "            mino = -1\n",
    "            for i in range(cnt,len(cards)): # 找到前cnt个数之后最大的奇数和偶数\n",
    "                if cards[i] % 2 == 0 and mino == -1:\n",
    "                    mino = cards[i]\n",
    "                if cards[i] % 2 != 0 and minj == -1:\n",
    "                    minj = cards[i]\n",
    "                if mino != -1 and minj != -1:\n",
    "                    break\n",
    "            if not(minj != -1 and maxo != -1) and not(maxj != -1 and mino != -1):\n",
    "                # 无法替换数使得和为偶数\n",
    "                return 0\n",
    "            if minj == -1 or maxo == -1 and not(maxj == -1 or mino == -1):\n",
    "                # 只能大偶数换小奇数\n",
    "                return score - maxj + mino\n",
    "            elif maxj == -1 or mino == -1 and not(minj == -1 or maxo == -1):\n",
    "                # 只能大奇数换小偶数\n",
    "                return score - maxo + minj\n",
    "            else:\n",
    "                # 都能换，要比较哪个更划算\n",
    "                if maxo - minj > maxj - mino:\n",
    "                    return score - (maxj - mino)\n",
    "                else:\n",
    "                    return score - (maxo - minj)\n",
    "        elif score % 2 == 0:\n",
    "            return score\n",
    "        else:\n",
    "            # cnt = len(cards)\n",
    "            return 0 \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        mod0 = []\n",
    "        mod1 = []\n",
    "\n",
    "        for x in cards:\n",
    "            if x & 1:\n",
    "                mod1.append(x)\n",
    "            else:\n",
    "                mod0.append(x)\n",
    "        \n",
    "        n0 = len(mod0)\n",
    "        n1 = len(mod1)\n",
    "        if n0 == 0 and cnt & 1 or cnt == len(cards) and n1 & 1:\n",
    "            return 0\n",
    "        \n",
    "        if n0 > cnt:\n",
    "            i = n0 - cnt\n",
    "            j = n1\n",
    "        else:\n",
    "            i = 0\n",
    "            cnt -= n0\n",
    "            if cnt & 1:\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "            j = n1 - cnt\n",
    "        \n",
    "        mod0.sort()\n",
    "        mod1.sort()\n",
    "\n",
    "        while i < n0 - 1 and j > 1 and mod0[i] + mod0[i+1] < mod1[j-1] + mod1[j-2]:\n",
    "            i += 2\n",
    "            j -= 2\n",
    "        \n",
    "        return sum(mod0[i:]) + sum(mod1[j:])\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int,count=0) -> int:\n",
    "        count=0\n",
    "        i,j=0,0\n",
    "        cards.sort(reverse=True)\n",
    "        if len(cards)<cnt:\n",
    "            return 0\n",
    "        else:\n",
    "            sum1=sum(cards[0:cnt])\n",
    "            if sum1%2==0:\n",
    "                return sum1\n",
    "            else:\n",
    "                odd1=[num for num in cards[0:cnt] if num%2==1]\n",
    "                even1=[num for num in cards[0:cnt] if num%2==0]\n",
    "                odd2=[num for num in cards[cnt:] if num%2==1]\n",
    "                even2=[num for num in cards[cnt:] if num%2==0]\n",
    "                if len(odd1)==0 and len(even1)>0 and len(odd2)>0:\n",
    "                    return sum1-even1[-1]+odd2[0]\n",
    "                elif len(odd1)>0 and len(even1)==0 and len(even2)>0:\n",
    "                    return sum1 -odd1[-1]+even2[0]\n",
    "                elif len(odd1)>0 and len(even1)>0 and len(odd2)>0 and len(even2)>0:\n",
    "                    return sum1+max(even2[0]-odd1[-1],odd2[0]-even1[-1])\n",
    "                elif len(odd2)==0 and len(odd1)>0 and len(even2)>0:\n",
    "                    return sum1-odd1[-1]+even2[0]\n",
    "                elif len(even2)==0 and len(even1)>0 and len(odd2)>0:\n",
    "                    return sum1-even1[-1]+odd2[0]\n",
    "                else:\n",
    "                    return 0\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int,count=0) -> int:\n",
    "        count=0\n",
    "        i,j=0,0\n",
    "        cards.sort(reverse=True)\n",
    "        even=[num for num in cards if num%2==0]\n",
    "        odd=[num for num in cards if num%2==1]\n",
    "        if cnt%2==1:\n",
    "            if len(even)>0:\n",
    "                count+=even[i]\n",
    "                cnt-=1\n",
    "                i+=1\n",
    "            else:\n",
    "                return 0\n",
    "        while cnt>0:\n",
    "            if len(even)>=i+2 and len(odd)>=j+2:\n",
    "                if even[i]+even[i+1]>odd[j]+odd[j+1]:\n",
    "                    count+=(even[i]+even[i+1])\n",
    "                    i+=2\n",
    "                else:\n",
    "                    count+=(odd[j]+odd[j+1])\n",
    "                    j+=2\n",
    "            elif len(even)>=i+2:\n",
    "                count += (even[i] + even[i+1])\n",
    "                i+=2\n",
    "            elif len(odd)>=j+2:\n",
    "                count+=(odd[j]+odd[j+1])\n",
    "                j+=2\n",
    "            else:\n",
    "                return 0\n",
    "            cnt-=2\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        odds,evens=[],[]\n",
    "        cards.sort()\n",
    "        for n in cards:\n",
    "            if n%2:\n",
    "                odds.append(n)\n",
    "            else:\n",
    "                evens.append(n)\n",
    "        ans = 0\n",
    "        while cnt:\n",
    "            if cnt>=2:\n",
    "                a,b = 0,0\n",
    "                if len(odds)>=2:\n",
    "                    a = odds[-1]+odds[-2]\n",
    "                if len(evens)>2 or (len(evens)==2 and cnt%2==0):\n",
    "                    b = evens[-1]+evens[-2]\n",
    "                elif len(evens)==1:\n",
    "                    b = evens[-1]\n",
    "                if a>=b:\n",
    "                    ans += a\n",
    "                    odds.pop()\n",
    "                    odds.pop()\n",
    "                    cnt -= 2\n",
    "                else:\n",
    "                    ans += b\n",
    "                    cnt -= 1\n",
    "                    evens.pop()\n",
    "                    if len(evens)>=1:\n",
    "                        cnt -= 1\n",
    "                        evens.pop()\n",
    "                if a==b==0:\n",
    "                    return 0\n",
    "            else:\n",
    "                if evens:\n",
    "                    ans += evens.pop()\n",
    "                    cnt -= 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        ji, ou = [0], [0]\n",
    "        for i in sorted(cards, reverse=True):\n",
    "            if i % 2:\n",
    "                ji.append(ji[-1] + i)\n",
    "            else:\n",
    "                ou.append(ou[-1] + i)\n",
    "        ret, max_ji = 0, cnt // 2\n",
    "        while max_ji >= 0:\n",
    "            tmp, ji_id = 0, max_ji * 2\n",
    "            if len(ji) > ji_id and len(ou) > cnt - ji_id:\n",
    "                tmp += ji[ji_id] if ji_id > 0 else 0\n",
    "                tmp += ou[cnt - ji_id] if cnt - ji_id > 0 else 0\n",
    "                ret = max(ret, tmp)\n",
    "            max_ji -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        cnt_list = cards[0:-cnt]\n",
    "        print(cnt_list)\n",
    "        cnt_list = cnt_list[::-1]\n",
    "        oringals = cards[-cnt:]\n",
    "        if not sum(oringals)%2:\n",
    "            return sum(oringals)\n",
    "        list_oringal = [x %2 for x in cards]\n",
    "        print(list_oringal)\n",
    "        change1 = [0,0]\n",
    "        change2 = [0,0]\n",
    "\n",
    "        for i in range(0,len(oringals)):\n",
    "            if not list_oringal[-cnt+i] and not change1[0]:\n",
    "                change1[0] = cards[-cnt+i]\n",
    "            elif list_oringal[-cnt+i] and not change1[1]:\n",
    "                change1[1] = cards[-cnt+i]\n",
    "        for i in range(1,len(cnt_list)+1):\n",
    "            if not list_oringal[-cnt-i] and not change2[0]:\n",
    "                change2[0] = cards[-cnt-i]\n",
    "            elif list_oringal[-cnt-i] and not change2[1]:\n",
    "                change2[1] = cards[-cnt-i]\n",
    "        print(change1,change2)\n",
    "        b = [-1000]*2\n",
    "        if change1[0] and change2[1]:\n",
    "            b[0] = change2[1]-change1[0]\n",
    "        if change1[1] and change2[0]:\n",
    "            b[1] = change2[0]-change1[1]\n",
    "        if max(b) == -1000:\n",
    "            return 0\n",
    "        return sum(oringals)+max(b)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        selected = []\n",
    "        max_odd_out, max_even_out = float('-inf'), float('-inf')        \n",
    "        for c in cards:\n",
    "            if len(selected) == cnt and selected[0] < c:\n",
    "                c = heappushpop(selected, c)\n",
    "                \n",
    "            if len(selected) < cnt:\n",
    "                heappush(selected, c)\n",
    "            elif c % 2 == 0:\n",
    "                max_even_out = max(max_even_out, c)\n",
    "            else:\n",
    "                max_odd_out = max(max_odd_out, c)\n",
    "        \n",
    "        odd_cnt = 0\n",
    "        min_odd_in, min_even_in = float('inf'), float('inf')\n",
    "        for c in selected:\n",
    "            if c % 2 == 1:\n",
    "                odd_cnt += 1\n",
    "                min_odd_in = min(min_odd_in, c)\n",
    "            else:\n",
    "                min_even_in = min(min_even_in, c)\n",
    "\n",
    "\n",
    "        ans = sum(selected)\n",
    "        if odd_cnt % 2 == 1:\n",
    "            ans += max(max_even_out - min_odd_in, max_odd_out - min_even_in)\n",
    "            \n",
    "        return 0 if ans == float('-inf') else ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        l, r = [], []\n",
    "        l_, r_ = -1, -1\n",
    "        for i in cards :\n",
    "            if i % 2 == 0 :\n",
    "                r.append(i)\n",
    "            else :\n",
    "                l.append(i)\n",
    "        r.sort()\n",
    "        l.sort()\n",
    "        ans = 0\n",
    "        if cnt % 2 == 1 :\n",
    "            if r == [] :\n",
    "                return 0\n",
    "            ans += r[-1]\n",
    "            r.pop()\n",
    "            cnt -= 1\n",
    "        while cnt > 0 :\n",
    "            if len(r) > 1 :\n",
    "                r_ = r[-1] + r[-2] \n",
    "            else :\n",
    "                r_ = -1\n",
    "            if len(l) > 1: \n",
    "                l_ = l[-1] + l[-2]\n",
    "            else :\n",
    "                l_ = -1\n",
    "            if l_ != -1 or r_ != -1 :\n",
    "                ans += max(l_, r_)\n",
    "                if l_ > r_ :\n",
    "                    l.pop()\n",
    "                    l.pop()\n",
    "                else :\n",
    "                    r.pop()\n",
    "                    r.pop()\n",
    "            else :\n",
    "                return 0\n",
    "            cnt -= 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        odd, even = [0], [0]\n",
    "        for card in cards:\n",
    "            if card & 1:\n",
    "                odd.append(odd[-1] + card)\n",
    "            else:\n",
    "                even.append(even[-1] + card)\n",
    "        ans = 0\n",
    "        for k in range(0, len(odd), 2):\n",
    "            if 0 <= cnt - k < len(even): \n",
    "                ans = max(ans, odd[k] + even[cnt-k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "\n",
    "\n",
    "        cards = sorted(cards)[::-1]\n",
    "\n",
    "        s_list = []\n",
    "        for i in range(0, cnt):\n",
    "        \n",
    "            s_list.append(cards[i])\n",
    "\n",
    " \n",
    "\n",
    "        if sum(s_list) % 2 == 0:\n",
    "            return sum(s_list)\n",
    "        if sum(s_list) % 2 != 0 and cnt == len(cards):\n",
    "            return 0\n",
    "\n",
    "        date = 0\n",
    "        date2 = 0\n",
    "        for x in s_list[::-1]:\n",
    "            if x % 2 != 0:\n",
    "                date = x\n",
    "                break\n",
    "        for x in s_list[::-1]:\n",
    "            if x % 2 == 0:\n",
    "                date2 = x\n",
    "                break\n",
    "     \n",
    "\n",
    "        s = 0\n",
    "        s2 = 0\n",
    "        for i in range(cnt, len(cards)):\n",
    "            if cards[i] % 2 != 0:\n",
    "                s = cards[i]\n",
    "                break\n",
    "\n",
    "        for i in range(cnt, len(cards)):\n",
    "            if cards[i] % 2 == 0:\n",
    "                s2 = cards[i]\n",
    "                break\n",
    "        if date - s2 > 0 and date2 - s > 0:\n",
    "            date_min = min(abs(date - s2), abs(date2 - s))\n",
    "        elif date - s2 > 0 and date2 - s <= 0:\n",
    "            date_min = date - s2\n",
    "        else:\n",
    "            date_min = date2 - s\n",
    "\n",
    "        date = sum(s_list) -  date_min\n",
    "        if date % 2 == 0:\n",
    "            return date\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort()\n",
    "        cnt_list = cards[0:-cnt]\n",
    "        print(cnt_list)\n",
    "        cnt_list = cnt_list[::-1]\n",
    "        oringals = cards[-cnt:]\n",
    "        if not sum(oringals)%2:\n",
    "            return sum(oringals)\n",
    "        list_oringal = [x %2 for x in cards]\n",
    "        print(list_oringal)\n",
    "        change1 = [0,0]\n",
    "        change2 = [0,0]\n",
    "\n",
    "        for i in range(0,len(oringals)):\n",
    "            if not list_oringal[-cnt+i] and not change1[0]:\n",
    "                change1[0] = cards[-cnt+i]\n",
    "            elif list_oringal[-cnt+i] and not change1[1]:\n",
    "                change1[1] = cards[-cnt+i]\n",
    "        for i in range(1,len(cnt_list)+1):\n",
    "            if not list_oringal[-cnt-i] and not change2[0]:\n",
    "                change2[0] = cards[-cnt-i]\n",
    "            elif list_oringal[-cnt-i] and not change2[1]:\n",
    "                change2[1] = cards[-cnt-i]\n",
    "        print(change1,change2)\n",
    "        b = [-1000]*2\n",
    "        if change1[0] and change2[1]:\n",
    "            b[0] = change2[1]-change1[0]\n",
    "        if change1[1] and change2[0]:\n",
    "            b[1] = change2[0]-change1[1]\n",
    "        if max(b) == -1000:\n",
    "            return 0\n",
    "        return sum(oringals)+max(b)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\r\n",
    "        cards.sort(reverse=True)\r\n",
    "        odd, even = [0], [0]  # 前缀和数组（向右偏移一个单位）\r\n",
    "        for card in cards:\r\n",
    "            if card & 1:\r\n",
    "                odd.append(odd[-1] + card)\r\n",
    "            else:\r\n",
    "                even.append(even[-1] + card)\r\n",
    "        \r\n",
    "        # 枚举奇数个数\r\n",
    "        ans = 0\r\n",
    "        for k in range(0, len(odd), 2):  # 原序列中取偶数个奇数\r\n",
    "            if 0 <= cnt - k < len(even):  # 原序列中取足够个偶数\r\n",
    "                ans = max(ans, odd[k] + even[cnt-k])  # 排序后前面的数字是最大的，O(1)得到它们的和\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        odd, even = [0], [0]  # 前缀和数组（向右偏移一个单位）\n",
    "        for card in cards:\n",
    "            if card & 1:\n",
    "                odd.append(odd[-1] + card)\n",
    "            else:\n",
    "                even.append(even[-1] + card)\n",
    "        \n",
    "        # 枚举奇数个数\n",
    "        ans = 0\n",
    "        for k in range(0, len(odd), 2):  # 原序列中取偶数个奇数\n",
    "            if 0 <= cnt - k < len(even):  # 原序列中取足够个偶数\n",
    "                ans = max(ans, odd[k] + even[cnt-k])  # 排序后前面的数字是最大的，O(1)得到它们的和\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "\n",
    "        def change(cards, m):\n",
    "            page = -1\n",
    "            for i in cards:\n",
    "                if i%2 == m:\n",
    "                    page = i\n",
    "                    break\n",
    "            return page\n",
    "\n",
    "        cards = sorted(cards)\n",
    "        item = sum(cards[-cnt:])\n",
    "        cards_j = [i for i in cards[0:-cnt] if i%2==1]\n",
    "        cards_o = [i for i in cards[0:-cnt] if i%2==0]\n",
    "        if item % 2 == 0:\n",
    "            return item\n",
    "        else:\n",
    "            ##奇数换偶数\n",
    "            item_c = 0\n",
    "            if cards_o:\n",
    "                ##item是奇数的情况肯定是有奇数的\n",
    "                item_c = max(item - change(cards[-cnt:], 1) + cards_o[-1], item_c)\n",
    "\n",
    "            #偶数换奇数\n",
    "            if cards_j:\n",
    "                #item是奇数的情况下不能说明cards里面有偶数，需要进行判断\n",
    "                page = change(cards[-cnt:], 0)\n",
    "                if page != -1: ##说明存在偶数\n",
    "                    item_c = max(item - change(cards[-cnt:], 0) + cards_j[-1], item_c)\n",
    "                else:\n",
    "                    #page=-1说明不存在偶数，也不需要进行偶数替换为奇数\n",
    "                    item_c = max(0, item_c)\n",
    "            \n",
    "            return item_c\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        odd, even = [0], [0]\n",
    "        for card in cards:\n",
    "            if card & 1:\n",
    "                odd.append(odd[-1] + card)\n",
    "            else:\n",
    "                even.append(even[-1] + card)\n",
    "        ans = 0\n",
    "        for k in range(0, len(odd), 2):\n",
    "            if 0 <= cnt -k < len(even):\n",
    "                ans = max(ans, odd[k] + even[cnt-k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        even = []\n",
    "        odd = []\n",
    "        for c in cards:\n",
    "            if c%2==0:\n",
    "                even.append(c)\n",
    "            else:\n",
    "                odd.append(c)\n",
    "        even.sort()\n",
    "        odd.sort()\n",
    "        total = 0\n",
    "        cot = 0\n",
    "        e_idx = len(even)-1\n",
    "        o_idx = len(odd)-1\n",
    "        if cnt%2==1:\n",
    "            if len(even)==0: return 0\n",
    "            total += even[e_idx]\n",
    "            e_idx -= 1\n",
    "            cot += 1\n",
    "\n",
    "        while cot<cnt:\n",
    "            if e_idx>=1 and o_idx>=1:\n",
    "                if (even[e_idx]+even[e_idx-1])>(odd[o_idx]+odd[o_idx-1]):\n",
    "                    total = total + even[e_idx] + even[e_idx-1]\n",
    "                    e_idx -= 2\n",
    "                else:\n",
    "                    total = total + odd[o_idx] + odd[o_idx-1]\n",
    "                    o_idx -= 2\n",
    "                cot += 2\n",
    "            elif e_idx>=1:\n",
    "                total = total + even[e_idx] + even[e_idx-1]\n",
    "                e_idx -= 2\n",
    "                cot += 2 \n",
    "            elif o_idx>=1:\n",
    "                total = total + odd[o_idx] + odd[o_idx-1]\n",
    "                o_idx -= 2\n",
    "                cot+=2\n",
    "            else:\n",
    "                return 0\n",
    "            pass\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        selected = []\n",
    "        pending = []\n",
    "        for c in cards:\n",
    "            if len(selected) == cnt and selected[0] < c:\n",
    "                pending.append(heappushpop(selected, c))\n",
    "            elif len(selected) < cnt:\n",
    "                heappush(selected, c)\n",
    "            else:\n",
    "                pending.append(c)\n",
    "        \n",
    "        n = len(cards)\n",
    "        ans = sum(selected)\n",
    "        m = sum(1 for c in selected if c % 2 == 1)\n",
    "        \n",
    "        if m % 2 == 1:\n",
    "            a = -min (c for c in selected if c % 2 == 1) + max((c for c in pending if c % 2 == 0), default=float('-inf'))\n",
    "            b = -min ((c for c in selected if c % 2 == 0), default=float('inf')) + max((c for c in pending if c % 2 == 1), default=float('-inf'))\n",
    "            ans += max(a,b)\n",
    "        return 0 if ans == float('-inf') else ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        ji, ou = [0], [0]\n",
    "        for i in sorted(cards, reverse=True):\n",
    "            if i % 2:\n",
    "                ji.append(ji[-1] + i)\n",
    "            else:\n",
    "                ou.append(ou[-1] + i)\n",
    "        ret, max_ji = 0, cnt // 2\n",
    "        while max_ji >= 0:\n",
    "            tmp, ji_id = 0, max_ji * 2\n",
    "            if len(ji) > ji_id and len(ou) > cnt - ji_id:\n",
    "                tmp += ji[ji_id] if ji_id > 0 else 0\n",
    "                tmp += ou[cnt - ji_id] if cnt - ji_id > 0 else 0\n",
    "                ret = max(ret, tmp)\n",
    "            max_ji -= 1\n",
    "        return ret\n",
    "\n",
    "# 作者：清风Python\n",
    "# 链接：https://leetcode.cn/problems/uOAnQW/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse=True)\n",
    "        even_psum, odd_psum = [], []\n",
    "        for c in cards:\n",
    "            if c % 2 == 0:\n",
    "                if len(even_psum) == 0:\n",
    "                    even_psum.append(c)\n",
    "                else:\n",
    "                    even_psum.append(even_psum[-1] + c)\n",
    "            else:\n",
    "                if len(odd_psum) == 0:\n",
    "                    odd_psum.append(c)\n",
    "                else:\n",
    "                    odd_psum.append(odd_psum[-1] + c)\n",
    "        max_score = 0\n",
    "        for num_odd in range(0, min(cnt, len(odd_psum)) + 1, 2):\n",
    "            num_even = cnt - num_odd\n",
    "            if num_even > len(even_psum):\n",
    "                continue\n",
    "            score = 0\n",
    "            if num_odd > 0:\n",
    "                score += odd_psum[num_odd - 1]\n",
    "            if num_even > 0:\n",
    "                score += even_psum[num_even - 1]\n",
    "            max_score = max(max_score, score)\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        selected = []\n",
    "        pending = []\n",
    "        for c in cards:\n",
    "            if len(selected) == cnt and selected[0] < c:\n",
    "                pending.append(heappushpop(selected, c))\n",
    "            elif len(selected) < cnt:\n",
    "                heappush(selected, c)\n",
    "            else:\n",
    "                pending.append(c)\n",
    "        \n",
    "        n = len(cards)\n",
    "        ans = sum(selected)\n",
    "        m = sum(1 for c in selected if c % 2 == 1)\n",
    "\n",
    "        print(selected, pending)\n",
    "\n",
    "        if m % 2 == 1:\n",
    "            a = -min (c for c in selected if c % 2 == 1) + max((c for c in pending if c % 2 == 0), default=float('-inf'))\n",
    "            b = -min ((c for c in selected if c % 2 == 0), default=float('inf')) + max((c for c in pending if c % 2 == 1), default=float('-inf'))\n",
    "            ans += max(a,b)\n",
    "        return 0 if ans == float('-inf') else ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        cards.sort(reverse = True)\n",
    "        odd = [0]\n",
    "        even = [0]\n",
    "        for card in cards:\n",
    "            if card % 2 == 0:\n",
    "                even.append(card+even[-1])\n",
    "            else:\n",
    "                odd.append(card+odd[-1])\n",
    "        \n",
    "        temp = 0\n",
    "        for k in range(0, len(odd), 2):\n",
    "            if cnt - k >= len(even):\n",
    "                continue\n",
    "            if cnt - k < 0:\n",
    "                break\n",
    "            if odd[k] + even[cnt - k] > temp:\n",
    "                temp = odd[k] + even[cnt-k]\n",
    "        return temp\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards, cnt) -> int:\n",
    "        if cnt > len(cards) :\n",
    "            return 0\n",
    "\n",
    "        cardsoddpre = [0]\n",
    "        cardsevenpre = [0]\n",
    "        res = 0\n",
    "        cards.sort(reverse=True)\n",
    "        for card in cards:\n",
    "            if card % 2 :\n",
    "                cardsoddpre.append(card+cardsoddpre[-1])\n",
    "            else :\n",
    "                cardsevenpre.append(card+cardsevenpre[-1])\n",
    "        lodd = len(cardsoddpre) - 1\n",
    "        lenve = len(cardsevenpre) - 1\n",
    "\n",
    "        for i in range(0,min(lodd,cnt)+1,2):\n",
    "            if lenve >= cnt - i :\n",
    "                res = max(res,cardsoddpre[i]+cardsevenpre[cnt-i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        odd = [0]\n",
    "        even = [0]\n",
    "        res = 0\n",
    "        cards.sort(reverse=True)\n",
    "        for card in cards:\n",
    "            if card % 2:\n",
    "                odd.append(card + odd[-1])\n",
    "            else:\n",
    "                even.append(card + even[-1])\n",
    "        lodd = len(odd) - 1\n",
    "        leven = len(even) - 1\n",
    "\n",
    "        for i in range(0, min(lodd, cnt) + 1, 2):\n",
    "            if leven >= cnt - i:\n",
    "                res = max(res, odd[i] + even[cnt - i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxmiumScore(self, cards: List[int], cnt: int) -> int:\n",
    "        # 计算最大的有效得分 \n",
    "        length = len(cards)             # 代表卡牌的张数\n",
    "        cards.sort(reverse = True)\n",
    "        # print(cards)       [9,8,2,1]\n",
    "\n",
    "        odd = [0]        # 存放奇数的数组\n",
    "        even = [0]       # 存放偶数的数组\n",
    "\n",
    "        for i in range(length):\n",
    "            if cards[i] % 2 != 0:\n",
    "                odd.append(odd[-1] + cards[i])          # odd[-1]表示最后一个元素\n",
    "            else:\n",
    "                even.append(even[-1] + cards[i])\n",
    "\n",
    "        # print(odd)    [0, 9, 10]\n",
    "        # print(even)   [0, 8, 10]\n",
    "\n",
    "        res = []\n",
    "        for i in range(0,len(odd),2):\n",
    "            if  0<= cnt - i < len(even):\n",
    "                res.append(odd[i] + even[cnt-i])\n",
    "        if not res:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(res)\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
